package cn.algorithm;

/**
 * @author: lizemin
 * @version: 1.0
 */
public class Test03 {
    public static int[] insertion_sort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int position = i;//保存当前临时值的索引, 每当一个数往右移后, 当前临时值的索引-1, 可以保证它最后可以插入到正确的空隙之中.
            int temp = arr[i];
            while (position > 0 && arr[position-1] > temp){
                //大于当前值, 就往右移
                arr[position] = arr[position-1];
                //同时当前值的索引-1
                position -= 1;
            }
            arr[position] = temp;
        }
        return arr;
    }

    //这是一个main方法,是程序的入口
    public static void main(String[] args) {
        int[] unsorted_array = new int[]{12,23,56,2,5};
        int[] sorted_array = insertion_sort(unsorted_array);
        for (int i : sorted_array) {
            System.out.print(i+"\t");

        }

    }


}
